﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CharmL.Helper {
    public static class ListExtension {
        public static void AddWithOrder(this List<int> list, int newValue) {
            int mid, first = 0, last = list.Count - 1;
            while (first <= last) {
                mid = (first + last) / 2;
                if (newValue < list[mid]) {
                    last = mid - 1;
                } else if (newValue > list[mid]) {
                    first = mid + 1;
                } else {
                    break;
                }
            }
            list.Insert(first, newValue);
        }

        
        public static new string ToDisplayString(this List<int> list) {
            return string.Join(";", list);
        }

        /// <summary>
        /// The following items are in list1 but not list2
        /// </summary>
        /// <param name="list1"></param>
        /// <param name="list2"></param>
        /// <returns></returns>
        public static List<int> SetDifference(List<int> list1, List<int> list2) {
            //TODO improve this method or measure perf between linq and handle manually
            List<int> differenceQuery = list1.Except(list2).ToList();
            return differenceQuery;
        }
        public static void AddUnique(this List<int> list, int newValue) {
            int mid, first = 0, last = list.Count - 1;
            while (first <= last) {
                mid = (first + last) / 2;
                if (newValue < list[mid]) {
                    last = mid - 1;
                } else if (newValue > list[mid]) {
                    first = mid + 1;
                } else {
                    //don't add
                    return;
                }
            }
            list.Insert(first, newValue);
        }

        public static bool IsSuperSetOf(this List<int> parent, List<int> child) {
            int parentIndex = 0;
            if (child.Count == 0) return true;
            if (parent.Count < child.Count) return false;
            for (int i = 0; i < child.Count; i++) {
                bool isFind = false;
                for (int j = parentIndex; j < parent.Count; j++) {
                    if (parent[j] == child[i]) {
                        parentIndex = j + 1;
                        isFind = true;
                        break;
                    }
                }
                if (!isFind) {
                    return false;
                }
            }
            return true;
        }

        public static bool IsAncestorOf(this List<int> ancestor, List<int> descendant) {
            return IsSuperSetOf(descendant, ancestor);
        }

        public static bool IsDescendantOf(this List<int> descendant, List<int> ancestor) {
            return IsSuperSetOf(descendant, ancestor);
        }

        public static bool IsSubSetOf(this List<int> child, List<int> parent) {
            int i, j;
            if (child.Count > parent.Count) return false;
            for (i = 0, j = 0; i < child.Count && j < parent.Count; ) {
                if (child[i] < parent[j]) return false;
                else if (child[i] > parent[j]) ++j;
                else {
                    ++i;
                    ++j;
                }
            }
            if (i < child.Count) return false;
            return true;
            //if (iset.size() > ia->iset.size()) return false;
            //for (i = 0, j = 0; i < iset.size() && j < ia->iset.size(); ) {
            //    if (iset[i] < ia->iset[j]) return false;
            //    else if (iset[i] > ia->iset[j]) ++j;
            //    else {
            //        ++i;
            //        ++j;
            //    }
            //}
            //if (i < iset.size()) return false;
            //return true;
            //if (parent.Count == 0) return true;
            //return IsSuperSetOf(parent, child);
        }

        public static bool IsEqual(this List<int> list1, List<int> list2) {
            if (list1.Count != list2.Count) {
                return false;
            }
            for (int i = 0; i < list1.Count; i++) {
                if (list1[i] != list2[i]) {
                    return false;
                }
            }
            return true;
        }

        public static List<int> IntersectWith(this List<int> list1, List<int> list2) {
            List<int> res = new List<int>();
            bool next = true;
            int i1 = 0;
            int i2 = 0;
            int c1 = list1.Count;
            int c2 = list2.Count;
            do {
                if (i1 >= c1 || i2 >= c2) {
                    next = false;
                } else {
                    if (list1[i1] == list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                        i2++;
                    } else if (list1[i1] < list2[i2]) {
                        i1++;
                    } else {
                        i2++;
                    }
                }
            } while (next);
            return res;
        }

        public static List<int> UnionWith(this List<int> list1, List<int> list2) {
            List<int> res = new List<int>();
            bool next = true;
            int i1 = 0;
            int i2 = 0;
            int c1 = list1.Count;
            int c2 = list2.Count;
            do {
                if (i1 >= c1 || i2 >= c2) {
                    if (i1 >= c1) {
                        //add c2 as the end of new list
                        for (int i = i2; i < c2; i++) {
                            res.Add(list2[i]);

                        }
                    } else if (i2 >= c2) {
                        for (int i = i1; i < c1; i++) {
                            res.Add(list1[i]);

                        }
                    }
                    next = false;
                } else {
                    if (list1[i1] == list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                        i2++;

                    } else if (list1[i1] < list2[i2]) {
                        res.Add(list1[i1]);
                        i1++;
                    } else {
                        res.Add(list2[i2]);
                        i2++;
                    }
                }
            } while (next);
            return res;
        }
    }
}
